#
# @lc app=leetcode.cn id=35 lang=python3
#
# [35] 搜索插入位置
#

# @lc code=start
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        #solution1:顺序查找
        # for i in range(len(nums)):
        #     if nums[i] >= target: return i
        
        # return len(nums)
            
        #soulution2:半数值查找
        # numsLen = len(nums)
        # lowIndex = 0
        # highIndex = numsLen - 1
        
        # while (highIndex - lowIndex) > 1:
        #     half = int((highIndex - lowIndex) / 2)
        #     if nums[lowIndex + half] == target:
        #         return lowIndex + half
        #     else:
        #         if target > nums[lowIndex + half]:
        #             lowIndex += half
        #         else:
        #             highIndex = lowIndex + half
        
        # if target > nums[highIndex]:
        #     return highIndex + 1
        # elif target == nums[highIndex]:
        #     return highIndex
        # elif target > nums[lowIndex]:
        #     return lowIndex + 1
        # else:
        #     return lowIndex
        
        #soulution3:半数值查找2
        numsLen = len(nums)
        lowIndex = 0
        highIndex = numsLen - 1
        
        while highIndex > lowIndex:
            half = int((highIndex - lowIndex) / 2)
            if nums[lowIndex + half] == target:
                return lowIndex + half
            else:
                if target > nums[lowIndex + half]:
                    lowIndex += (half+1)
                else:
                    highIndex = lowIndex + half - 1
        
        if target > nums[highIndex]:
            return highIndex + 1
        elif target == nums[highIndex]:
            return highIndex
        else:
            return lowIndex
            
# @lc code=end

